The competition between local and global driving forces is significant in awide variety of naturally occurring branched networks. We have investigated theimpact of a global minimization criterion versus a local one on the structureof spanning trees. To do so, we consider two spanning tree structures - thegeneralized minimal spanning tree (GMST) defined by Dror et al. [1] and ananalogous structure based on the invasion percolation network, which we termthe generalized invasive spanning tree or GIST. In general, these twostructures represent extremes of global and local optimality, respectively.Structural characteristics are compared between the GMST and GIST for a fixedlattice. In addition, we demonstrate a method for creating a series ofstructures which enable one to span the range between these two extremes. Twostructural characterizations, the occupied edge density (i.e., the fraction ofedges in the graph that are included in the tree) and the tortuosity of thearcs in the trees, are shown to correlate well with the degree to which anintermediate structure resembles the GMST or GIST. Both characterizations arestraightforward to determine from an image and are potentially useful tools inthe analysis of the formation of network structures.
展开▼
